//Given two strings s and t of lengths m and n respectively, return the minimum 
//window in s which will contain all the characters in t. If there is no such wind
//ow in s that covers all characters in t, return the empty string "". 
//
// Note that If there is such a window, it is guaranteed that there will always 
//be only one unique minimum window in s. 
//
// 
// Example 1: 
// Input: s = "ADOBECODEBANC", t = "ABC"
//Output: "BANC"
// Example 2: 
// Input: s = "a", t = "a"
//Output: "a"
// 
// 
// Constraints: 
//
// 
// m == s.length 
// n == t.length 
// 1 <= m, n <= 105 
// s and t consist of English letters. 
// 
//
// 
//Follow up: Could you find an algorithm that runs in O(m + n) time? Related Top
//ics 哈希表 双指针 字符串 Sliding Window 
// 👍 1168 👎 0


package leetcode.editor.cn;

import java.util.*;

//Java：Minimum Window Substring
class P76MinimumWindowSubstring {
    public static void main(String[] args) {
        Solution solution = new P76MinimumWindowSubstring().new Solution();
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String minWindows(String str1, String str2) {
            String[][] memo = new String[str1.length() + 1][str2.length() + 1];
            for (int i = 0; i <= str1.length(); i++) {
                memo[i][0] = "";
            }
            for (int i = 0; i <= str2.length(); i++) {
                memo[0][i] = "";
            }
            for (int i = 1; i <= str1.length(); i++) {
                for (int j = 1; j <= str2.length(); j++) {
                    if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                        memo[i][j] = memo[i - 1][j - 1] + str1.charAt(i - 1);
                    } else {
                        memo[i][j] = memo[i][j - 1].length() > memo[i - 1][j].length() ? memo[i][j - 1] : memo[i - 1][j];
                    }
                }
            }
            return memo[str1.length()][str2.length()].equals("") ? "-1" : memo[str1.length()][str2.length()];

        }

        Map<Character, Integer> ori = new HashMap<Character, Integer>();
        Map<Character, Integer> cnt = new HashMap<Character, Integer>();

        public String minWindow(String s, String t) {
            int tLen = t.length();
            for (int i = 0; i < tLen; i++) {
                char c = t.charAt(i);
                ori.put(c, ori.getOrDefault(c, 0) + 1);
            }
            int l = 0, r = -1;
            int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
            int sLen = s.length();
            while (r < sLen) {
                ++r;
                if (r < sLen && ori.containsKey(s.charAt(r))) {
                    cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (check() && l <= r) {
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        ansL = l;
                        ansR = l + len;
                    }
                    if (ori.containsKey(s.charAt(l))) {
                        cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }

        public boolean check() {
            Iterator iter = ori.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry) iter.next();
                Character key = (Character) entry.getKey();
                Integer val = (Integer) entry.getValue();
                if (cnt.getOrDefault(key, 0) < val) {
                    return false;
                }
            }
            return true;
        }

        public String minWindowEas(String s, String t) {
            if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
                return "";
            }
            //维护两个数组，记录已有字符串指定字符的出现次数，和目标字符串指定字符的出现次数
            //ASCII表总长128
            int[] need = new int[128];
            int[] have = new int[128];

            //将目标字符串指定字符的出现次数记录
            for (int i = 0; i < t.length(); i++) {
                need[t.charAt(i)]++;
            }

            //分别为左指针，右指针，最小长度(初始值为一定不可达到的长度)
            //已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的起始位置
            int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0;
            while (right < s.length()) {
                char r = s.charAt(right);
                //说明该字符不被目标字符串需要，此时有两种情况
                // 1.循环刚开始，那么直接移动右指针即可，不需要做多余判断
                // 2.循环已经开始一段时间，此处又有两种情况
                //  2.1 上一次条件不满足，已有字符串指定字符出现次数不满足目标字符串指定字符出现次数，那么此时
                //      如果该字符还不被目标字符串需要，就不需要进行多余判断，右指针移动即可
                //  2.2 左指针已经移动完毕，那么此时就相当于循环刚开始，同理直接移动右指针
                if (need[r] == 0) {
                    right++;
                    continue;
                }
                //当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时，count才会+1
                //是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符，不需要挨个比对字符出现的次数
                if (have[r] < need[r]) {
                    count++;
                }
                //已有字符串中目标字符出现的次数+1
                have[r]++;
                //移动右指针
                right++;
                //当且仅当已有字符串已经包含了所有目标字符串的字符，且出现频次一定大于或等于指定频次
                while (count == t.length()) {
                    //挡窗口的长度比已有的最短值小时，更改最小值，并记录起始位置
                    if (right - left < min) {
                        min = right - left;
                        start = left;
                    }
                    char l = s.charAt(left);
                    //如果左边即将要去掉的字符不被目标字符串需要，那么不需要多余判断，直接可以移动左指针
                    if (need[l] == 0) {
                        left++;
                        continue;
                    }
                    //如果左边即将要去掉的字符被目标字符串需要，且出现的频次正好等于指定频次，那么如果去掉了这个字符，
                    //就不满足覆盖子串的条件，此时要破坏循环条件跳出循环，即控制目标字符串指定字符的出现总频次(count）-1
                    if (have[l] == need[l]) {
                        count--;
                    }
                    //已有字符串中目标字符出现的次数-1
                    have[l]--;
                    //移动左指针
                    left++;
                }
            }
            //如果最小长度还为初始值，说明没有符合条件的子串
            if (min == s.length() + 1) {
                return "";
            }
            //返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串
            return s.substring(start, start + min);
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}